package katas.recursion;

import java.util.LinkedList;
import java.util.List;

public class Parenthesis {
	
	public List<String> generateParenthesis(int n){
		List<String> list = new LinkedList<String>();
		_generateParenthesis(0, 0, n, new String(), list);
		return list;
	}
	
	private void _generateParenthesis(int open, int closed, int n, String s, 
			List<String> list){
		if(closed == n)
			list.add(s);
		else{
			if(open < n)
				_generateParenthesis(open + 1, closed, n, s + "(", list);
			if(open > closed)
				_generateParenthesis(open, closed + 1, n, s + ")", list);
		}
	}
	
	public static void main(String[] args) {
		Parenthesis p = new Parenthesis();
		System.out.println(p.generateParenthesis(3));
	}
}
